package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _236_lowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //1.维护节点与其对应的父节点关系
        Map<Integer, TreeNode> parent = new HashMap<>();
        dfs(root, parent);

        //2. 从节点p开始，依次访问它的祖先
        Set<Integer> visited = new HashSet<>();
        while (p!=null){
            visited.add(p.val);
            p = parent.get(p.val);
        }

        //3. 从节点q开始，依次访问它的祖先
        // 如果第一次遇到了P的祖先的话， 那么这个祖先就是最近的公共祖先
        while (q!=null){
            if(visited.contains(q.val)){return q;}
            q = parent.get(q.val);
        }
        return null;

    }

    private void dfs(TreeNode node, Map<Integer, TreeNode> parent) {
        if (node == null) {return;}

        if (node.left != null) {parent.put(node.left.val, node);}
        if (node.right != null) {parent.put(node.right.val, node);}

        dfs(node.left, parent);
        dfs(node.right, parent);
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {return null;}
        if (root == p || root == q) {return root;}
        TreeNode left = lowestCommonAncestor1(root.left, p, q);
        TreeNode right = lowestCommonAncestor1(root.right, p, q);

        if (left == null) {return right;}
        if (right == null) {return left;}
        return root;
    }
}
